import csv
import numpy as np
import pyproj
from scipy.spatial.distance import cdist
import random
import matplotlib.pyplot as plt
import pandas as pd
import utm

# 读取CSV文件并提取经纬度坐标
def read_coordinates_from_csv(file_path):
    df = pd.read_csv(file_path)
    coordinates = df[['经度', '纬度']].values
    coordinates = []
    for _,row in df.iterrows():   
        log=row['经度']
        lat=row['纬度']
        utm_coords=utm.from_latlon(lat,log)
        coordinates.append(np.array([utm_coords[0],utm_coords[1]]))
    coordinates = np.array(coordinates)
    return coordinates


# 粒子群算法（PSO）求解最短路径问题
class PSO:
    def __init__(self, distance_matrix, num_particles=30, max_iter=100, alpha=1.0, beta=1.0, gamma=1.0):
        self.distance_matrix = distance_matrix
        self.num_points = distance_matrix.shape[0]
        self.num_particles = num_particles
        self.max_iter = max_iter
        self.alpha = alpha  # 惯性权重
        self.beta = beta  # 个体最优权重
        self.gamma = gamma  # 全局最优权重
        self.particles = [self.init_particle() for _ in range(num_particles)]
        self.gbest = min(self.particles, key=lambda x: x['fitness'])
    
    def init_particle(self):
        particle = np.random.permutation(self.num_points)
        fitness = self.calculate_fitness(particle)
        return {'position': particle, 'velocity': np.zeros(self.num_points), 'pbest': particle, 'fitness': fitness}
    
    def calculate_fitness(self, particle):
        fitness = 0
        for i in range(self.num_points - 1):
            fitness += self.distance_matrix[particle[i], particle[i + 1]]
        fitness += self.distance_matrix[particle[-1], particle[0]]  # 回到起点
        return fitness
    
    def update_velocity(self, particle):
        inertia = self.alpha * particle['velocity']
        cognitive = self.beta * np.random.rand() * (particle['pbest'] - particle['position'])
        social = self.gamma * np.random.rand() * (self.gbest['position'] - particle['position'])
        new_velocity = inertia + cognitive + social
        return new_velocity
    
    def update_position(self, particle):
        new_position = particle['position'] + particle['velocity']
        new_position = np.mod(new_position, self.num_points)  # 保持在范围内
        return new_position.astype(int)
    
    def optimize(self):
        for _ in range(self.max_iter):
            for particle in self.particles:
                particle['velocity'] = self.update_velocity(particle)
                particle['position'] = self.update_position(particle)
                particle['fitness'] = self.calculate_fitness(particle['position'])
                
                if particle['fitness'] < self.calculate_fitness(particle['pbest']):
                    particle['pbest'] = particle['position']
                
                if particle['fitness'] < self.calculate_fitness(self.gbest['position']):
                    self.gbest = particle
    
    def get_best_path(self):
        return self.gbest['position']



# 主程序
def main(csv_file_path):
    # 读取CSV文件中的经纬度坐标
    coordinates = read_coordinates_from_csv(csv_file_path)

    # 计算距离矩阵
    distance_matrix = cdist(coordinates, coordinates, metric='euclidean')

    # 使用PSO算法求解最短路径问题
    pso = PSO(distance_matrix)
    pso.optimize()
    best_path = pso.get_best_path()
    plot_path(coordinates, best_path)

    # 输出最短路径
    print("最短路径:", best_path)
    print("路径长度:", pso.calculate_fitness(best_path))

def plot_path(coordinates, path):
    plt.figure()
    for i in range(len(path)):
        start = coordinates[path[i]]
        end = coordinates[path[(i + 1) % len(path)]]
        plt.plot([start[0], end[0]], [start[1], end[1]], 'bo-')
    plt.xlabel('Longitude')
    plt.ylabel('Latitude')
    plt.show()

if __name__ == "__main__":
    # 替换为你的CSV文件路径
    csv_file_path = "d:\Lenovo\Desktop\云南大学\空间数据挖掘\实验数据\data10_yn.csv"
    main(csv_file_path)
